﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.BinaryTreeCode
{
    //二叉搜索树（BST）是一个有序树
    //若它的左子树不空，则左子树上的所有节点的值均小于它的根节点的值
    //若它的右子树不空，则右子树上的所有节点的值均大于它的根节点的值
    //它的左右子树也分别为二叉搜索树

    //二叉搜索树的属性

    class AttriOfSearchTree
    {
        //====================================================力扣700 二叉搜索树中的搜索
        //给定二叉搜索树（BST）的根节点和一个值，你需要在BST中找到节点值等于给定值的节点。返回以该及诶点为跟的子树。如果节点不存在，返回null
        public TreeNode SearchBST(TreeNode root, int val)
        {//递归
            if (root == null || root.val == val)
                return root;

            if (root.val > val)
                return SearchBST(root.left, val);
            if (root.val < val)
                return SearchBST(root.right, val);
            return null;
        }
        //-----------------------------------------------------
        public TreeNode SearchBST_2(TreeNode root, int val)
        {//迭代
            while(root != null)
            {
                if (root.val > val)
                    root = root.left;
                else if (root.val < val)
                    root = root.right;
                else if (root.val == val)
                    return root;
            }
            return null;
        }

        //========================================================力扣98 验证二叉搜索树
        //给定一个二叉树，判断其是否是一个有效的二叉搜索树
        
        private List<int> vec;
        public bool IsValidBST(TreeNode root)
        {//思路：将二叉树按中序遍历转换为数组，然后判断是否是递增
            vec = new List<int>();
            Traversal(root);
            for(int i = 1;i<vec.Count;i++)
            {
                // 注意要小于等于，搜索树里不能有相同元素
                if (vec[i] <= vec[i - 1])
                    return false;
            }
            return true;
        }
        private void Traversal(TreeNode root)
        {
            if (root == null)
                return;
            Traversal(root.left);
            vec.Add(root.val);//将二叉搜索树转换为有序数组
            Traversal(root.right);
        }
        //-----------------------------------------------------
        //直接递归法
        private TreeNode pre = null;//用来记录前一个节点
        public bool IsValidBST_2(TreeNode root)
        {
            if (root == null)
                return true;
            bool left = IsValidBST_2(root.left);// 左

            // 中序遍历，验证遍历的元素是不是从小到大
            if (pre != null && pre.val >= root.val)// 中
                return false;
            pre = root;

            bool right = IsValidBST_2(root.right);// 右
            return left && right;
        }
        //-----------------------------------------------------
        //迭代法
        public bool IsValidBST_3(TreeNode root)
        {
            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode cur = root;
            TreeNode pre = null;//记录前一个节点
            while(cur != null || st.Count > 0)
            {
                if(cur != null)
                {
                    st.Push(cur);
                    cur = cur.left;//左
                }
                else
                {
                    cur = st.Pop();//中
                    if (pre != null && cur.val <= pre.val)
                        return false;
                    pre = cur;//保存前一个访问的节点

                    cur = cur.right;//右
                }
            }
            return true;
        }

        //=====================================================力扣530 二叉搜索树的最小绝对差
        //给你一颗所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值
        //树中至少有两个节点
        
        //二叉搜索树是有序的
        public int GetMinimumDifference(TreeNode root)
        {//使用中序遍历将二叉搜索树转换为数组
            list = new List<int>();
            Traversal_2(root);
            if (list.Count < 2)
                return 0;
            int result = int.MaxValue;
            for(int i  =1;i<list.Count;i++)
            {
                result = Math.Min(result, list[i] - list[i - 1]);
            }
            return result;
        }
        private List<int> list;
        private void Traversal_2(TreeNode root)
        {
            if (root == null)
                return;
            Traversal_2(root.left);
            list.Add(root.val);
            Traversal_2(root.right);
        }
        //-----------------------------------------------------
        public int GetMinimumDifference_2(TreeNode root)
        {//迭代法
            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode cur = root;
            TreeNode pre = null;
            int result = int.MaxValue;
            while(cur != null || st.Count > 0)
            {
                if(cur != null)
                {//访问到最底层
                    st.Push(cur);//将访问的节点放进栈
                    cur = cur.left;//左
                }
                else
                {
                    cur = st.Pop();//中
                    if(pre != null)
                    {
                        result = Math.Min(result, cur.val - pre.val);
                    }
                    pre = cur;
                    cur = cur.right;//右
                }
            }
            return result;
        }

        //================================================力扣501 二叉搜索树中的众数
        //给定一个由相同值的二叉搜索树（BST），找出BST中的所有众数（出现频率最高的数）
        //如果众数超过一个，不考虑输出顺序
        public int[] FindMode(TreeNode root)
        {//对于普通二叉树的通用方法
         //遍历二叉树，用map统计频率，然后取得高频词

            Hashtable map = new Hashtable();
            if (root == null)
                return new int[0];

            SearchBST(root, map);
            List<Tuple<int, int>> vec = new List<Tuple<int, int>>();
            List<int> result = new List<int>();
            foreach(int i in map.Keys)
            {
                vec.Add(new Tuple<int, int>(i, (int)map[i]));
            }

            vec.Sort(
                delegate(Tuple<int, int> A, Tuple<int, int> B)
                {
                    return B.Item2.CompareTo(A.Item2);
                });
            result.Add(vec[0].Item1);
            for (int i = 1;i< vec.Count;i++)
            {
                // 取最高的放到result数组中
                if (vec[i].Item2 == vec[0].Item2)
                    result.Add(vec[i].Item1);
                else
                    break;
            }
            return result.ToArray();

        }
        void SearchBST(TreeNode cur, Hashtable map)
        {//前序遍历统计频率
            if (cur == null)
                return;
            //中
            if (map.ContainsKey(cur.val))
            {
                map[cur.val] = (int)map[cur.val] + 1;
            }
            else
                map.Add(cur.val, 1);

            SearchBST(cur.left, map);//左
            SearchBST(cur.right, map);//右
        }
        //-----------------------------------------------------
        public int[] FindMode_2(TreeNode root)
        {//二叉搜索树，中序遍历就是有序的
            count = 0;
            maxCount = 0;
            result = new List<int>();
            SearchBST_3(root);
            return result.ToArray();

        }
        private TreeNode preNode = null;
        int count;//统计频率；
        int maxCount;//最大频率
        List<int> result;
        private void SearchBST_3(TreeNode cur)
        {
            if (cur == null)
                return;

            SearchBST_3(cur.left);//左

            if (preNode == null)//第一个节点
                count = 1;
            else if (preNode.val == cur.val)//与前一个节点数值相同
                count++;
            else//与前一个节点数值不同
                count = 1;

            preNode = cur;//更新上一个节点

            if (count == maxCount)//如果和最大值相同，就放进result
                result.Add(cur.val);

            if (count > maxCount) //如果计数大于最大值频率
            {
                maxCount = count;//更新最大值频率
                result.Clear();//result的元素失效了，清空它
                result.Add(cur.val);
            }

            SearchBST_3(cur.right);//右
            return;
        }
        //-----------------------------------------------------
        public int[] FindMode_3(TreeNode root)
        {//迭代法 中序遍历

            Stack<TreeNode> st = new Stack<TreeNode>();
            TreeNode cur = root;
            TreeNode pre = null;
            int maxCount = 0;
            int count = 0;
            List<int> result = new List<int>();
            while(cur != null || st.Count > 0)
            {
                if(cur != null)
                {// 指针来访问节点，访问到最底层
                    st.Push(cur);// 将访问的节点放进栈
                    cur = cur.left; // 左
                }
                else
                {
                    cur = st.Pop();// 中

                    if (pre == null) // 第一个节点
                        count = 1;
                    else if(pre.val == cur.val) // 与前一个节点数值相同
                        count++;
                    else//与前一个节点数值不同
                        count = 1;


                    if (count == maxCount)//如果和最大值相同，就放进result
                        result.Add(cur.val);

                    if (count > maxCount) //如果计数大于最大值频率
                    {
                        maxCount = count;//更新最大值频率
                        result.Clear();//result的元素失效了，清空它
                        result.Add(cur.val);
                    }
                    pre = cur;//更新上一个节点
                    cur = cur.right;//右
                }
            }
            return result.ToArray() ;
        }

        //======================================================力扣236 二叉树的最近公共祖先
        //给定一个二叉树，找到该树中两个指定节点的最近公共节点
        //公共节点：对于有根数T的两个节点p,q，最近公共节点表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {//思路：求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从低向上的遍历方式。
         //在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
         //要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
            if (root == q || root == p || root == null)
                return root;

            TreeNode left = LowestCommonAncestor(root.left, p, q);
            TreeNode right = LowestCommonAncestor(root.right, p, q);
            if (left != null && right != null)
                return root;
            if (left == null && right != null)
                return right;
            else if (left != null && right == null)
                return left;
            else
            {//left == null && right == null
                return null;
            }
        }

        //==========================================================力扣235 二叉搜索树的最近公共祖先
        //给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先
        public TreeNode LowestCommonAncestor_2(TreeNode  root, TreeNode p, TreeNode q)
        {//二叉搜索树是有序的，只要从上往下遍历的时候，cur节点是在[p,q]里，则说明cur是最近的公共祖先
            //递归法
            if (root == null)
                return root;
                                                     // 中                                
            if (root.val > p.val && root.val > q.val)// 左
            {
                TreeNode left = LowestCommonAncestor_2(root.left, p, q);
                if (left != null)
                    return left;
            }
            if(root.val < p.val && root.val < q.val)// 右
            {
                TreeNode right = LowestCommonAncestor_2(root.right, p, q);
                if (right != null)
                    return right;
            }

            //(root.val > p.val && root.val < q.val)
            return root;
        }
        //-----------------------------------------------------------------
        public TreeNode LowestCommonAncestor_3(TreeNode root, TreeNode p, TreeNode q)
        {//迭代法 思路同上
            while(root != null)
            {
                if (root.val > p.val && root.val > q.val)
                    root = root.left;
                else if (root.val < p.val && root.val < q.val)
                    root = root.right;
                else
                    return root;
            }
            return null;
        }


    }
}
